//Copyright (C) 2013 Julio Espindola
//
//This file is part of VSize Checkers.
//
//VSize Checkers is free software: you can redistribute it and/or modify
//it under the terms of the GNU General Public License as published by
//the Free Software Foundation, either version 3 of the License, or
//(at your option) any later version.
//
//VSize Checkers is distributed in the hope that it will be useful,
//but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//GNU General Public License for more details.
//
//You should have received a copy of the GNU General Public License
//along with VSize Checkers.  If not, see <http://www.gnu.org/licenses/>.

package checkers;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;

class Board implements java.io.Serializable
{
    static final byte ODD = (byte) 1; //0b0000_0001;
    static final byte UPPER_EDGE =  (byte) -128; //(byte) 0b1000_0000;
    static final byte LOWER_EDGE = (byte) 64; //0b0100_0000;
    static final byte LEFT_EDGE = (byte) 32; //0b0010_0000;
    static final byte RIGHT_EDGE = (byte) 16; //0b0001_0000;
    
    static final byte TURN = (byte) 1; //0b0000_0001;
    static final byte WHITE_WIN = (byte) 2; //0b0000_0010;
    static final byte BLACK_WIN = (byte) 4; //0b0000_0100;
    static final byte DRAW = (byte) 8; //0b0000_1000;
    static final byte GAME_OVER = (byte) 14; //0b0000_1110;
    
    static final int UPPER_LEFT = 0;
    static final int UPPER_RIGHT = 1;
    static final int LOWER_LEFT = 2;
    static final int LOWER_RIGHT = 3;
    static final int NUM_DIR = 3;
    
    byte[] squares;
    long hash;
    int add;
    int halfMove;
    int whiteMaterial, blackMaterial;
    
    private static final Piece[] pieces;
    static long zobrist[];
    
    static
    {
        pieces = new Piece[4];
        pieces[Piece.WHITE_PAWN >> 2] = new Pawn((byte) 0);
        pieces[Piece.BLACK_PAWN >> 2] = new Pawn(Piece.BLACK);
        pieces[Piece.WHITE_QUEEN >> 2] = new Queen((byte) 0);
        pieces[Piece.BLACK_QUEEN >> 2] = new Queen(Piece.BLACK);
    }
    
    final void initBoard(int size)
    {
        squares = new byte[(size*size)/2 + 1];
        squares[0] = 0;
        add = size/2;
        int numPieces = ((size/2)*(size-2))/2;
        
        for(int i=1; i<=numPieces; ++i)
            setPiece(i, Piece.BLACK_PAWN);
        
        for(int i=(squares.length-numPieces); i<squares.length; ++i)
            setPiece(i, Piece.WHITE_PAWN);
        
        for(int i=1; i<=size/2; ++i)
            squares[i] |= UPPER_EDGE;
        
        for(int i=squares.length-(size/2); i<squares.length; ++i)
            squares[i] |= LOWER_EDGE;
        
        for(int i=size/2+1; i<=squares.length-(size/2); i+=size)
            squares[i] |= LEFT_EDGE;
        
        for(int i=size/2; i<=squares.length-(size/2)-1; i+=size)
            squares[i] |= RIGHT_EDGE;
        
        
        for(int i=size/2+1; i<=squares.length-(size/2); i+=size)
        {
            for(int j=0; j<size/2; ++j)
                squares[i+j] |= ODD;
        }
    }
    
    final void initZobrist()
    {
        Random rand = new Random();
        zobrist = new long[(squares.length-1)*4+1];
        
        for(int i=0; i<zobrist.length; ++i)
            zobrist[i] = (rand.nextLong() & 9223372036854775807l); //0x7FFF_FFFF_FFFF_FFFFl
    }
    
    final void hashBoard()
    {
        hash = 0;
        
        for(int i=1; i<squares.length; ++i)
            if(!isFree(i))
                hash ^= zobrist[(i-1)*4 + (getPiece(i)>>2)];
        
        if((squares[0]&TURN)!=0)
            hash ^= zobrist[zobrist.length-1];
    }
    
    Board(int size)
    {
        initBoard(size);
        countPieces();
        initZobrist();
        hashBoard();
        Ai.table.resetTable();
        halfMove = 0;
    }
    
    Board(Board b)
    {
        squares = new byte[b.squares.length];
        System.arraycopy(b.squares, 0, squares, 0, squares.length);
        add = b.add;
        hash = b.hash;
        halfMove = b.halfMove;
        whiteMaterial = b.whiteMaterial;
        blackMaterial = b.blackMaterial;
    }
    
    int getStatus()
    {
        switch(squares[0]&GAME_OVER)
        {
            case WHITE_WIN: return 1;
            case BLACK_WIN: return 2;
            case DRAW: return 3;
            default: return 0;
        }
    }
    
    public boolean getTurn()
    {
        return (squares[0]&TURN) == 0;
    }
    
    byte getSquare(int index)
    {
        return squares[index];
    }
    
    boolean isFree(int index)
    {
        return (squares[index] & Piece.PIECE) == 0;
    }
    
    boolean isBlack(int index)
    {
        return (squares[index] & Piece.BLACK) != 0;
    }
    
    boolean isQueen(int index)
    {
        return (squares[index] & Piece.QUEEN) != 0;
    }
    
    void setPiece(int index, byte piece)
    {
        squares[index] = (byte) ((squares[index]&Piece.CLEAR) | piece);
    }
    
    byte getPiece(int index)
    {
        return (byte) (squares[index] & Piece.GET);
    }
    
    int getIndex(int index, int dir)
    {
        switch(dir)
        {
            case UPPER_LEFT:
                if((squares[index]&(Board.LEFT_EDGE|Board.UPPER_EDGE))==0)
                    return index - add - (squares[index]&ODD);
                break;
            case UPPER_RIGHT:
                if((squares[index]&(Board.RIGHT_EDGE|Board.UPPER_EDGE))==0)
                    return index - add+1 - (squares[index]&ODD);
                break;
            case LOWER_LEFT:
                if((squares[index]&(Board.LEFT_EDGE|Board.LOWER_EDGE))==0)
                    return index + add - (squares[index]&ODD);
                break;
            case LOWER_RIGHT:
                if((squares[index]&(Board.RIGHT_EDGE|Board.LOWER_EDGE))==0)
                    return index + add+1 - (squares[index]&ODD);
                break;
        }
        return -1;
    }
    
    boolean jumpable(int index, int dir, byte color)
    {
        int dest = getIndex(index, dir);
        return dest!=-1 && (squares[dest]&Piece.PIECE)==0 && (squares[index]&Piece.BLACK)!=color;
    }
    
    static void getMaxDepthJumps(ArrayList<Move> moves)
    {
        for(int i=0; i<moves.size(); ++i)
            if(moves.get(i).getSize() < Piece.maxSize)
                moves.remove(i--);
    }
    
    ArrayList<Move> findMoves()
    {
        Piece.maxSize = 0;
        ArrayList<Move> moves = new ArrayList<Move>(50);
        byte ok = (byte)(Piece.PIECE|(byte)((squares[0]&TURN)<<2));
        byte check = (Piece.PIECE|Piece.BLACK);
        
        for(int i=1; i<squares.length; ++i)
            if((squares[i]&check) == ok)
                pieces[(squares[i]&Piece.GET)>>2].getJumps(this, i, moves, new MJumps(i));
        
        if(moves.isEmpty())
        {
            for(int i=1; i<squares.length; ++i)
                if((squares[i]&check) == ok)
                    moves.addAll(pieces[(squares[i]&Piece.GET)>>2].getMoves(this, i));
        }
        else getMaxDepthJumps(moves);

        return moves;
    }
    
    public void checkForWin(ArrayList<Move> moves)
    {
        squares[0] ^= TURN;
        if(!hasPiecesLeft())
        {
            squares[0] |= (squares[0]&TURN)!=0?WHITE_WIN:BLACK_WIN;
            squares[0] ^= TURN;
            return;
        }
        
        squares[0] ^= TURN;
        if(!hasPiecesLeft() || moves.isEmpty())
            squares[0] |= (squares[0]&TURN)!=0?WHITE_WIN:BLACK_WIN;
    }
    
    ArrayList<Move> makeMove(Move m)
    {
        m.make(this);
        squares[0] ^= TURN;
        hash ^= zobrist[zobrist.length-1];
        
        ArrayList<Move> moves = findMoves();
        if(!hasPiecesLeft() || moves.isEmpty())
            squares[0] |= (squares[0]&TURN)!=0?WHITE_WIN:BLACK_WIN;
        else if(halfMove >= 25) squares[0] |= DRAW;
        
        return moves;
    }
    
    void undoMove(Move m)
    {
        m.undo(this);
        squares[0] &= TURN;
        squares[0] ^= TURN; 
        hash ^= zobrist[zobrist.length-1];
    }
    
    int evaluate()
    {
        switch(squares[0]&GAME_OVER)
        {
            case WHITE_WIN:
                return (squares[0]&TURN)==0 ? Ai.NEAR_INF : -Ai.NEAR_INF;
            case BLACK_WIN:
                return (squares[0]&TURN)==0 ? -Ai.NEAR_INF : Ai.NEAR_INF;
            case DRAW:
                return 0;
            default:
                return (squares[0]&TURN)==0 ? whiteMaterial-blackMaterial : blackMaterial-whiteMaterial;
        }
    }
    
    private boolean hasPiecesLeft()
    {
        return (squares[0]&TURN)==0 ? whiteMaterial>0 : blackMaterial>0;
    }
    
    public final void countPieces()
    {
        whiteMaterial = blackMaterial = 0;
        
        for(int i=1; i<squares.length; ++i)
            if(!isFree(i))
            {
                if(isBlack(i)) blackMaterial += isQueen(i) ? 3 : 1;
                else whiteMaterial += isQueen(i) ? 3 : 1;
            }
    }
    
    @Override
    public String toString()
    {
        String s="";
        for(int i=1; i<squares.length; ++i)
        {
            if(!isFree(i)) s += i + " : " + (getPiece(i)>>2) + "\n";
        }
        
        return s;
    }
    
    @Override
    public boolean equals(Object obj)
    {
        Board other = (Board) obj;
        
        for(int i=0; i<squares.length; ++i)
            if(squares[i] != other.squares[i])
                return false;
        
        return true;
    }
}
